package base;

import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;

import com.google.common.collect.ForwardingSortedSet;
import com.google.common.primitives.Ints;

/**
 * A singleton {@link Comparator} for use with {@link SortedSet}s of integers.  Sorts by set size, then
 * by order of elements - i.e., size 2 comes before size 3, for equal sizes 1, 2, 3 ... comes before
 * 1, 2, 4 ... sets.
 * <p>
 * For the {@link #markerSet(int)} result to work properly, those sets must contain only positive values.
 * @author Carl Pearson
 *
 */
public enum SmallestFirst implements Comparator<SortedSet<Integer>>{

	INSTANCE;
	
	@Override public int compare(SortedSet<Integer> o1, SortedSet<Integer> o2) {
			
			if (o1 == o2 || (o1.isEmpty() && o2.isEmpty())) return 0;
				
			//N.B. a marker set is designed to chop off everything smaller
			int result = o1.size() - o2.size(); // smaller set to the left, larger set to the right
			if (result!=0) return result;
			
			assert o1.size() == o2.size();
			
			result = o1.first() - o2.first();
			if (result!=0) return result;
			
			Iterator<Integer> o1Iter = o1.iterator();
			Iterator<Integer> o2Iter = o2.iterator();
			
			o1Iter.next(); o2Iter.next(); //bypass checked element
			
			while (o1Iter.hasNext())
				if ((result = Ints.compare(o1Iter.next(), o2Iter.next()))!=0) return result;
			
			return 0;
		}
		
//	static final Map<Integer,SortedSet<Integer>> markerCache = Maps.newHashMap();
	
	/**
	 * A set for splitting {@link SortedSet}s with {@link SmallestFirst#INSTANCE} as their
	 * comparator.
	 * <p>
	 * A marker set is otherwise non-functional.  Attempts to use it any other set context will
	 * probably throw a {@link NullPointerException}, though that is not guaranteed.
	 * @param dropSize the size of sets that come before the marker set -
	 * i.e., the set resulting from tail(markerSet(dropSize)) will contain sets only larger than dropSize.
	 * @return
	 */
	public static SortedSet<Integer> markerSet(final int dropSize) {
//		if (markerCache.containsKey(dropSize)) return markerCache.get(dropSize);
//		markerCache.put(dropSize, new MarkerSet(dropSize+1));
//		return markerCache.get(dropSize);
		return new MarkerSet(dropSize+1);
	}
	
	static class MarkerSet extends ForwardingSortedSet<Integer> {
		private final int size;
		MarkerSet(int size) { this.size = size; }
		@Override protected SortedSet<Integer> delegate() { return null; }
		@Override public boolean isEmpty() { return false; }
		@Override public int size() { return size; }
		@Override public Integer first() { return -1; }
		@Override public String toString() { return "marker set size: "+size; }
		@Override public boolean equals(Object other) {
			return (other instanceof MarkerSet) ? ((MarkerSet)other).size == size : false;
		}
		@Override public int hashCode() { return size; }
	}
}
